Problem statement: zenit17ckj

Jeden uzol, dva uzly…

Počet bodov: 35, časový limit: 1500ms

Šandyna sa nedávno hrala so špagátmi. Tentoraz si zobrala niekoľko horolezeckých lán a poviazala ich hlava-nehlava. Ostal jej nevzhľadný motanec lana. Rovnako, ako minule, ju zaujíma, ako najviac vie túto spleť natiahnuť. Keďže si Šandyna nechce dokaličiť ruky, lano môže napnúť iba medzi dvomi uzlami, koncom niektorého lana a uzlom, alebo dvoma koncami lana.

Vstup a výstup

Na prvom riadku dostanete čísla \(n\) a \(m\) (\(1 \leq n, m \leq 150\)) – počet lán a počet uzlov.

V druhom riadku vstupu je \(n\) celých čísel \(l_1, l_2 \ldots l_n\) (\(1 \leq l_i \leq 10^6\)) – dĺžky jednotlivých lán.

Nasleduje \(m\) riadkov, v každom z nich celé čísla \(s_1, x_1, s_2, x_2\) (\(1 \leq s_1, s_2 \leq n,\ 0 \leq x_1 \leq l_{s_1}, 0 \leq x_2 \leq l_{s_2}\)) označujúce, že lano \(s_1\) je vo vzdialenosti \(x_1\) od začiatku previazané s lanom \(s_2\) vo vzdialenosti \(x_2\) od jeho začiatku.

Vypíšte jedno číslo – najväčšiu možnú dĺžku, na ktorú vieme lano napnúť medzi dvoma uzlami, uzlom a koncom lana, alebo dvoma koncami lán¹.

Môžete predpokladať, že všetky laná držia pokope, čiže neexistujú také dve laná, ktoré vieme od seba potiahnuť ľubovoľne ďaleko. Taktiež môžete predpokladať, že odpoveďou je vždy celé číslo.

Príklad

Input:

2 1
10 6
1 3 2 1

Output:

12

Najvzdialenejší je koniec prvého a koniec druhého lana. Keď laná natiahneme, od konca prvého lana je vo vzdialenosti \(7\) jediný uzol a od uzla ku koncu druhého lana je to navyše \(5\).

Input:

1 1
10
1 1 1 9

Output:

2

Lano môže byť previazané aj samo so sebou. Keby sme lano naťahovali medzi obomi koncami, kvôli uzlu by sme ho natiahli iba na dĺžku 2. Začiatok lana a uzol sa dajú natiahnuť na dĺžku 1, rovnako ako koniec lana a uzol.